#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int max = 0;
        for (auto& e : nums)
        {
            max += e;
        }
        turn_max(nums, k, max);

        return max;
    }
    void turn_max(vector<int>& nums, int k, int& max)
    {
        if (k == 0)
        {
            return;
        }
        if (k % 2 == 0 && max >= (max - nums[0] + -nums[0]))
        {
            return;
        }
        max -= nums[0];
        nums[0] = -nums[0];
        max += nums[0];
        sort(nums.begin(), nums.end());
        turn_max(nums, k - 1, max);
    }
};